1. Technical Field
The present invention relates to an improved method and system for providing data communications and, in particular, to an improved method and system for providing data communications within a distributed computing network. Still more particularly, the present invention relates to an improved method and system of providing route determination information used to determine a route within a distributed computing network for data communications utilizing a distributed directory service.
2. Description of the Prior Art
A distributed data processing system typically consists of a number of data processors interconnected by a data communications network. In a distributed system, data and programs for processing the data may be stored at several network sites with the object of locating them near to the network locations at which they are most commonly accessed. This avoids dependence on a single central processor providing all processing functions and can reduce the data traffic and communications delays within the communications network. Distributed networks of processors are increasingly prevalent due to great technological advances in providing powerful processes at every level of the system (e.g. workstations with powerful processors are now able to run quite complex applications) and in providing communications networks to enable these processes to cooperate.
The importance of distributed processing has also increased with the increased potential for related users of information systems to share information, such as between different business enterprises who serve the same customers and who each may have their own respective intra-enterprise data communications facilities. Communications networks can be worldwide and of any size and complexity (the simple network configurations such as where all nodes are directly connected to a single central node or where every node is directly connected to every other are not feasible with networks of any significant size).
While computer networking has produced gains in productivity and efficiency, it has also introduced the problem of how to enable cooperation between disparate communication networks and operating platforms (which may be created by different vendors) so that they can interoperate, allowing businesses to integrate all of their data processing resources.
An essential requirement of distributed data processing systems is the provision of efficient routing of communications between cooperating processes which may be located at different network locations. Indeed, effective routing is required in any communications network. Existing networking software performs the routing function in a variety of ways, generally involving large amounts of network configuration data being held at each network node. The term network node is used herein to refer to any network entity from and to which data communications may be routed, comprising one or more computer programs installed on a particular hardware device and having a defined name and/or address and a particular location within the network. The prior art routing techniques can be divided into source routing and destination routing techniques. In source routing, each node in the network has knowledge of the exact route to be used to send messages to all possible destinations. This precomputed route information is included in the message or data packet as it starts its journey. Each intervening node along the predefined route uses the route definition in the message in order to make forwarding decisions. The problem with this approach, particularly for message-based systems where the network topology may change dynamically, is how to endow the nodes with knowledge of routes. (The term "message" is used hereafter as a general reference to a unit of data which is transferred between processes, and therefore includes all messages and data packets, and all units of data transmitted between processes whether the data is for application-processing or relates to systems management or monitoring).
Source routing is disclosed, for example, in WO 93/16539. Each device maintains a routing list which gives the preferred communication path to every other device in the network. Dynamic reconfiguration of the network is dealt with by each device periodically sending a beacon message to all other devices, informing them of its presence in the network. Communication paths having the shortest path length are stored at each node.
While beacon messaging has the advantage of not requiring operator input, it also has the problem, particularly in large and complex networks, of considerably increasing network traffic unless imperfect knowledge of the network status is accepted (as in WO 93/16539 where beaconing is periodic rather than in response to every change). If out-of-date information is used for routing determinations, network resources will be wasted and communication delays introduced by attempts to create routes which include unavailable nodes or links.
In destination routing, each node again maintains a routing table but the complete source-to-destination route for a particular message transmission is not precomputed and added to the message. Instead, each node along the route between source and destination generally determines where next to send the message in its journey towards the destination. A number of different approaches are known:
Local static routing involves static tables being maintained at the nodes in the network by the system administrators at each node. The term static implies that the tables are not updated by a programmed algorithm. The need for human intervention is a weakness in a complex, dynamically changing network. PA1 Centralized static routing involves tables at the various network nodes being updated by a system administrator sitting at a central "point of control" (POC) node. This approach assumes that the POC can gain remote access to the controlled nodes. PA1 Centralized adaptive routing involves an algorithm updating node routing tables automatically. The assumption of centralized techniques is that a designated POC is sent information from all nodes in the network regarding the state of their local network links. The POC first uses this information to build a topological model of the entire network, and then sends each node of the network the information it needs to build its local routing table. With this approach, there is a strong dependence on the POC node being operational at all times. PA1 Local adaptive routing involves the selection of an outgoing link using a local heuristic. Examples include is algorithms that route based on message queue length, or on random selection, or on flooding (replicating the message on several links) or on observation or arrival patterns. PA1 starting with a first one (start node) of the source node or the destination node, identifying from the directory which network nodes (first neighbor nodes) are directly connected to the start node, and then determining whether any first neighbor node is the second one (end node) of said source and destination nodes; PA1 responsive to a negative result of said determination, identifying from the directory which network nodes (second neighbor nodes) other than the start node are directly connected to each of said first neighbors, and determining whether any second neighbor node is the end node; PA1 and continuing this progressive evaluation of partial routes via intermediate connected nodes until the route-determination process identifies a node which is directly connected to the end node, thereby determining a complete route for communications between the source node and the destination node. The directory is updated when the network configuration changes, by updating the directory's stored configuration information for each node for which the set of that node's directly connected nodes is changed.
None of the above routing techniques works well in an environment in which the network configuration is dynamically changing, because of the considerable overhead in updating the information held by each of the network nodes together with the need both to ensure that interconnected nodes hold consistent information and to avoid the processing delays that result if communications have to wait while updates are performed, or while the POC is unavailable. The information which each node maintains for routing purposes must be reliably updatable if there is to be provision for the possibility of the network itself being reconfigured.
EP-A-0258654 discloses a network traffic routing and network management system in which a central computer has access to stored tariff data and uses this to determine on behalf of other nodes a routing policy which is then transmitted to the network nodes as routing instructions which are specific for each originating node and each destination.
Distributed adaptive routing is another technique known from the prior art. EP-A-0510822 discloses a distributed technique in which a circulating status table (CST) is forwarded to all nodes connected within a network, with each node updating the CST with its link and status information and obtaining from the CST and storing the most recently updated configuration information for the network. The function of monitoring the network topology is thus distributed among each of the nodes of the network, monitor software resident in each node being responsible for providing status information about that node and its communication links from locally-stored information which is periodically updated by the CST. This solution has severe limitations in large networks or networks where reconfigurations are frequent, since the CST may become out of date before it reaches all of the network nodes and because different nodes may have inconsistent information for unacceptably long periods of time.
EP-A-0568737 discloses routing logic for adaptive and distributed routing. Routing choices are made using local transmission delay information in combination with the "hop distance" (number of nodes along the route) to the destination node. The local transmission delay information is estimated by evaluating at the source node, prior to data transmission, partial routes between source and destination by means of signalling. Hop distances are calculated and compiled in a table at the particular node at which the calculation is performed, for use in selecting a partial route for data packet transmission. Since hop distance is a less dynamic parameter than most forms of topological information, an assumption of the reliability of the hop distance parameter is made without much signalling, reducing the signalling and processing overhead as compared with logic which requires evaluation of the entire route.
EP-A-0426911 discloses an example routing management system in which each node includes a dynamic routing table containing a plurality of machine identifiers and, for each, the next place in the network to which a message for that machine should be directed. The system of EP-A-0426911 requires a database of machine listings, including update and routing information for each machine. The update information identifies the parts of the system which need to be updated to maintain consistency if some part of the machine's database entry is changed, including information as to which nodes require their dynamic routing tables to be updated in response to a change to that entry. All relevant nodes are sent updated routing information. The amount of information that must be held by each node and the overhead in updating that information are both considerable.
It is desirable here to refer to the layered architecture structure of networks, for later reference. International architecture standards have been, and are being, developed to promote commonality and heterogeneous interoperability for all users of information technology and communications. A significant aspect of these standards are the international standards for Open Systems Interconnection (OSI) and the Systems Network Architecture (SNA). OSI and SNA both define seven-layer communications architectures in which each layer makes use of the services of the layer below and provides services to the layer above. This layered architecture structure can be represented as in FIG. 1 (taken from R. J. Cypser, "Communications for Cooperating Systems OSI--OSI, SNA, and TCP/IP", Addison-Wesley, 1991, p48. The figure uses OSI names but is generally applicable to OSI or SNA. (The somewhat different names and approximate relationships between the SNA and OSI layers are represented by Cypser in the above-referenced book at page 47--Cypser's FIG. 3.2).
The lower three layers of the OSI and SNA communication architectures (the "transport service providers") include transmission subnetworks such as X.25 packet switching networks, LANs, ISDN, WANs, and other network and link layer protocols. Subnetworks will generally be divisible from the whole network into separate administrative units known as "cells", cell names generally being important for inter-cell communications. The networks may be highly complex, with many intermediate nodes being involved in any data transmission between source and destination nodes. Layer 1 of the architecture is the physical connections between adjacent nodes, wires along which electrical signals pass.
Layer 2 is the data link control layer, providing fixed path configurations (point-to-point connections, multipoint connections and LANs) and possibly link-layer flow control and link-layer error-recovery. Layer 2 may also provide multi-path routing between intermediate nodes.
Layer 3 provides a subnetwork (e.g. LAN, ISDN) for multi-path routing between source and destination nodes and provides flow control within the subnetwork (e.g. multiplexing, segmenting). Layer 3 also provides internetworking links between the subnetworks.
The transport control layer 4 oversees communication across multiple underlying transport facilities. Source-to-destination transport reliability (e.g. by enciphering of data or sequence numbering) and flow control are provided by layer 4. OSI layer 4 (and the top of layer 3) corresponds to the position in the layered structure of common communications protocols such as TCP/IP (Transmission Control Protocol/Internet Protocol suite of protocols) and NetBIOS, being the providers of end-to-end reliable stream delivery.
Layer 5 is a data exchange layer providing a set of common signals used by applications for synchronization and regulation of the data exchange. Layer 6, the presentation services layer, interprets API verbs and converts data where communicating end users require different syntax and formats.
Layer 7 is the layer providing immediate service support for applications (called the application services layer in OSI and transaction services layer in SNA). Layer 7 provides file transfer, directory services, store-and-forward messaging, and system management. Directories are repositories for information, directory services being the combination of the repositories and processes which make use of the repository information to locate a named resource, i.e. name resolution. Originally created solely for the purpose of enabling client processes to contact a suitable server within the same network cell, directory services have recently been developed to provide other name resolution functions such as look-up access for nodes outside the immediate cell. Global directory services are also now available for name resolution between different cells in addition to the directories, for intra-cell resolution. Nodes initially contact a local directory service to locate a named resource, and if the local directory does not contain the particular resource name then the global directory service will be contacted to point to a different local directory service (generally using cell name resolution) which has the information for locating the required resource. Distributed directory services are also known in the art, directory information being located at network sites where it is commonly required.
Hereafter, the terminology of OSI is used to identify different layers of the network architecture. This use of terminology specific to a particular layered network architecture model is used for simplicity and to aid understanding and should not be interpreted as a limitation on the applicability of the present invention.